Accurate and efficient monitoring of network internal states (e.g., delays and loss rates on individual links) is important for various network operations such as network planning, routing reselection, resource allocation, and fault diagnosis. Various conventional techniques (e.g., Tivoli Netcool and Network Manager) typically rely on directly measuring the metrics of interest through local monitoring agents running on internal nodes. Such direct measurement is typically most applicable to tightly integrated networks (e.g., enterprise networks, data center). FIG. 1 shows an example of such direct measurement in connection with network 100. In particular, this FIG. 1 shows direct measurement carried out from each of servers E, F, G and H.
Loosely integrated networks (e.g., Internet, third-party networks, legacy networks and smart city networks) typically require a different approach as (all or part of) the network internal states are not directly accessible by the monitoring system. This second approach is network tomography.
Network tomography (see, L F. Lo Presti, N. Duffield, J. Horowitz, and D. Towsley, “Multicast-based inference of network-internal delay distributions,” IEEE/ACM Trans. Networking, 2002) provides a light-weight alternative. Network tomography aims at inferring internal link metrics from externally measurable end-to-end path metrics between monitors. Measurement is collected by sending probe packets from a source monitor to a destination monitor along a selected path. The link metrics involved in this path are accordingly measured as a sum path metric at the destination monitor. Combining all possible path measurements, network tomography is essentially an inverse problem with the purpose of reconstructing the link level information based on their accumulated performance in the corresponding monitor-to-monitor paths.
FIG. 2 shows an example of such network tomography in connection with network 200. As seen in this FIG. 2, network tomography provides for inferring internal link/path metrics from external probes between vantage points or monitors (e.g., servers E/H and G/F).
However, network tomography conventionally has certain limitations. For example, one goal is to infer network internal state (e.g., link metrics) from external observation (e.g., external-to-external probes). This may be attempted via inverting the measurement matrix (see FIG. 3 showing an example network and matrix). However, a pitfall is that such a matrix is not always invertible (rank deficient) and monitor placement is important. In this regard, although the number of paths is much larger than the number of links, most paths (all except at most n paths, n being the number of links) are linearly dependent, thus essentially providing no new information. Accordingly, one question is how to place monitors to make the metric invertible?
Various conventional solutions in monitor deployment focus on complete link identification. Specifically, R. Kumar and J. Kaur, “Practical beacon placement for link monitoring using network tomography,” JSAC, 2006 and Y. Breitbart, F. F. Dragan, and H. Gobjuka, “Effective monitor placement in Internet networks,” Journal of Networks, vol. 4, no. 7, 2009 try to minimize the number of required monitors; however, internal support (ICMP (Internet Control Message Protocol)) must be available in R. Kumar and J. Kaur, “Practical beacon placement for link monitoring using network tomography,” JSAC, 2006 and all link metrics are assumed to be binary in Y. Breitbart, F. F. Dragan, and H. Gobjuka, “Effective monitor placement in Internet networks,” Journal of Networks, vol. 4, no. 7, 2009. In recent work (L. Ma, T. He, K. K. Leung, D. Towsley, and A. Swami, “Topological conditions for identifying additive link metrics via end-to-end path measurements,” submitted to INFOCOM 2013), an optimal monitor deployment algorithm is developed that uses the minimum number of monitors to identify all link metrics under an arbitrary network topology.
Referring now to FIG. 4A showing a basic network and FIG. 4B showing an extended network, a further discussion will now be made with respect to minimum deployment for complete identification (in this example, the “basic network” is the original topology of the network under consideration as illustrated in FIG. 4A and the “extended network” is the original topology plus added virtual monitors and links as illustrated in FIG. 4A). In this regard, “Topological conditions for identifying additive link metrics via end-to-end path measurements,” L. Ma, T. He, K. K. Leung, D. Towsley, and A. Swami had established “iff” conditions (that is, necessary and sufficient conditions) on monitor placement for unique link identification (i.e., computation of link metrics) using cycle-free probes. Still referring to FIGS. 4A and 4B, this process uses at least 3 monitors and the extended network must be 3-vertex-connected.
That is, the conditions imply that each bi/triconnected component (see the network 500 of FIG. 5) of FIG. 5) needs ≧3 “monitors” (cutvertices/monitors). This results in the minimum deployment for complete identification. In use, the minimum number monitors needed can be large (for example, an ATT network of backbone and access routers (see, http://www.cs.washington.edu/research/networking/rocketfuel/interactive/7018us.html) may need 88 monitors 108 nodes). Further, here is a question of how to place monitors to minimize uncertainty in network state under limited budget? In practical deployment, network operators may have a limited budget for monitor deployment. Moreover, not all internal links are equally important to monitor. Therefore, in various embodiments techniques to selectively deploy monitors are provided (e.g., to identify high-value states while minimizing uncertainty on the rest).